class ListNode:
    def __init__(self, item):
        self.val = item
        self.next = None


class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None

        pa, pb = headA, headB

        while pa != pb:
            pa = pa.next if pa else headB
            pb = pb.next if pb else headA

        return pa


# 创建相交链表示例
# 链表A: a1 -> a2 -> c1 -> c2 -> c3
# 链表B: b1 -> b2 -> b3 -> c1 -> c2 -> c3

# 创建公共部分
c1 = ListNode(8)
c2 = ListNode(4)
c3 = ListNode(5)
c1.next = c2
c2.next = c3

# 创建链表A
a1 = ListNode(4)
a2 = ListNode(1)
a1.next = a2
a2.next = c1  # 连接到公共节点

# 创建链表B
b1 = ListNode(5)
b2 = ListNode(6)
b3 = ListNode(1)
b1.next = b2
b2.next = b3
b3.next = c1  # 连接到公共节点

solution = Solution()
result = solution.getIntersectionNode(a1, b1)

# 输出结果
print(result.val if result else None)  # 应该输出 8
